package study.datastructure.dp;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2025-02-16 11:20
 */

/**
 2025/2/16,
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 动态规划
 */
public class s1 {

    /**
     * 爬楼梯
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     *
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     *
     * dp[i] = dp[i-1] + dp[i-2]
     *
     * 循环 迭代  i - > n
     *
     * 边界情况
     * dp[1] = 1;
     * dp[2] = 2;
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        int curr = 0;
        int prev1 = 1;
        int prev2 = 2;

        for (int i = 3; i < n+1; i++) {
           curr = prev1 + prev2;
           prev1 = prev2;
           prev2 = curr;
        }
        return curr;
    }

    /**
     * 杨辉三角
     * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
     *[
     *  [        1  ]
     *     [   1    1 ]
     *       1   2    1
     *      1  3    3   1
     * ]
     *
     * triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
     *
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {

        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        for (int i = 1; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = triangle.get(i -1);
            // 首元素
            row.add(1);

            // 中间元素
            for (int j = 1; j < i; j++) {
                //row[j] = prevRow[j-1] + prevRow[j];
                row.add(prevRow.get(j-1) + prevRow.get(j));
            }

            // 尾元素
            row.add(1);

            triangle.add(row);
        }

        return triangle;
    }

}
